package leetcode_day._2022._202201._1120;

import java.util.Arrays;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/1/18 9:21
 * 最小时间差
 * 算法：排序、模拟 + 数学
 * 一天有 24 * 60 minute
 * 如果 timePoints 的长度大于 1440，那么就有两天相同，直接返回 0
 *
 */
public class _18_539 {
    public static void main(String[] args) {
        System.out.println(new _18_539().findMinDifference_moni(Arrays.asList("05:31", "22:08", "00:35")));
    }

    public int findMinDifference(List<String> timePoints) {
        int m = timePoints.size();
        int[] times = new int[m];
        for (int i = 0; i < m; i++) {
            String[] split = timePoints.get(i).split(":");
            times[i] = Integer.parseInt(split[0]) * 60 + Integer.parseInt(split[1]);
        }
        Arrays.sort(times);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < m - 1; i++) ans = Math.min(ans, times[i + 1] - times[i]);
        return Math.min(ans, times[0] + 1440 - times[m - 1]);
    }

    public int findMinDifference_moni(List<String> timePoints) {
        int m = timePoints.size();
        // 一天有 24 * 60 分钟
        if (m >= 1440) return 0;
        // 23:00, 1:00, 8:00
        int[] times = new int[1440 * 2 + 10];
        for (String timePoint : timePoints) {
            String[] split = timePoint.split(":");
            int hour = Integer.parseInt(split[0]), minute = Integer.parseInt(split[1]);
            times[hour * 60 + minute]++;
            times[hour * 60 + minute + 1440]++;
        }
        int ans = 1440, last = -1;
        for (int i = 0; i <= 1440 * 2 && ans != 0; i++) {
            if (times[i] == 0) continue;
            if (times[i] > 1) ans = 0;
            else if (last != -1) ans = Math.min(ans, i - last);
            last = i;
        }
        return ans;
    }

}
